import javax.transaction.TransactionRequiredException;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * user:likai
 * Date:2022-11-03
 * Time:16:49
 */
class BinaryTree{
    class TreeNode{
        public int val;
        public TreeNode left;
        public TreeNode right;
        public TreeNode(int val){
            this.val=val;
        }
    }
    TreeNode root=null;
    //搜索
    public TreeNode search(int val){
        if(root==null){
            return null;
        }
        TreeNode cur=root;
        while(cur!=null){
            if(val>cur.val){
                cur=cur.right;
            } else if (val< cur.val) {
                cur=cur.left;
            }else {
                return cur;
            }
        }
        return null;
    }
    //建立树
    public boolean insert(int val){
        //如果根为空
        if(root==null){
            root.val=val;
            return true;
        }
        //如果根不为空
        TreeNode cur=root;
        TreeNode pre=null;
        while(cur!=null){
            if(cur.val>val){
                pre=cur;
                cur=cur.left;
            } else if (cur.val<val) {
                pre=cur;
                cur=cur.right;
            }else {
                return false;
                //已经存在这个数值
            }
        }
        TreeNode node=new TreeNode(val);
        if(pre.val>val){
            pre.left=node;
        }else{
            pre.right=node;
        }
        return true;
    }
    //去掉
    public boolean remove(int val){
        if(root==null){
            return false;
        }
        //先找到它
        TreeNode cur=root;
        TreeNode pre=null;
        while (cur!=null){
            if(cur.val>val){
                pre=cur;
                cur=cur.left;
            } else if (cur.val<val) {
                pre=cur;
                cur=cur.right;
            }else {
                //等于，找到了
                removeChild(pre,cur);
            }
        }
        return false;
    }
    public void removeChild(TreeNode parent,TreeNode cur){
        if(cur.left==null){//删除的左边是空的
            if(cur==root){//如果是删除根
                root=cur.right;
            } else if (cur==parent.left) {
                parent.left=cur.right;
            }else {
                parent.right=cur.right;
            }
        } else if (cur.right==null) {//删除的右边是空的
            if(cur==root){//如果是删除根
                root=cur.left;
            } else if (cur==parent.left) {
                parent.left=cur.left;
            }else {
                parent.right=cur.left;
            }
        }else{//删除的左右都不为空
            TreeNode target=cur.right;
            TreeNode targetParent=cur;
            while(target.left!=null){
                targetParent=target;
                target=target.left;
            }
            if(targetParent.right==target){
                targetParent.right=target.right;
            }
            targetParent.left=target.right;
        }
    }
}
public class Test {
}
